#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

class NumberCombine:
    def __init__(self, target_num):
        self.num = target_num
        self.memory = {}            # dp的记忆体, 空间换时间, 递归中已经计算过的子问题做记录

        self.hit_memory_cnt = 0

    def partion_cnt(self):
        cnt = 0
        for part_n in range(1, self.num+1):
            cnt += self.partion_cnt_rec_n(self.num, part_n)

        return cnt

    def partion_cnt_rec_n(self, num, part_n):
        # 将num分割成part_n份
        key = num, part_n
        res = self.memory.get(key)
        if res is not None:
            return res

        if num == part_n:
            # print('hit equal')
            return 1

        if 1 == part_n:
            # print('hit 1')
            return 1

        # 分情况讨论分成part_n份
        cnt = self.split(num, part_n)
        self.memory[key] = cnt
        return cnt

    def split(self, num, n):
        # 分情况讨论分成part_n份
        assert num > n

        cnt = 0
        # 如果num分成n份, 那么最大的数是num - (n-1): 其它n-1个数最小, 都是1, 剩下一个数最大
        remain = num - (n-1)

        for first_num in range(1, remain+1):
            # 分成n份, 第一个数的可能性first_num
            # 但是注意这其中包含了所有的可能的(重复的)情况:
            # 比如(5, 2): 5个数分成两个数, 第一个数是3, 那么剩下只能是2
            # 如果第一个数是2, 那么剩下只能是3(这两种情况, 相当于同构)
            cnt += self.partion_cnt_rec_n(num-first_num, n-1)

        return cnt


def test():
    for i in range(1, 100):
        n = NumberCombine(i)
        assert n.partion_cnt() == 2**(i-1)

def main():
    print("start main")
    test()


if __name__ == "__main__":
    main()
